/*
   @Copyright:LeetCode
   @Author:   tjyemail
   @Problem:  http://leetcode.com/problems/longest-consecutive-sequence
   @Language: C++
   @Datetime: 19-09-03 11:16
   */

// Method 1, Union-Find-Set, Time 24ms, Space 10MB
class Solution {
	int father(unordered_map<int,int> &F, int x){
		if(F.count(x)==0) return x;
		for(; F[x]!=x; x=F[x]);
		return x;
	}
public:
	int longestConsecutive(vector<int>& nums) {
		unordered_map<int,int> F;
		for(const int &x:nums){
			if(x!=INT_MAX && F.count(x+1)) F[x]=father(F,x+1);
			else F[x]=father(F,x);
			if(x!=INT_MIN && F.count(x-1)) F[x-1]=F[F[x]];
		}
		int len=0;
		for(const int &x:nums)
			len=max(len,father(F,x)-x+1);
		return len;
	}
};

// Method 2, Hashset Optimization, Time 16ms, Space 9.1MB
class Solution {
public:
	int longestConsecutive(vector<int>& nums) {
		unordered_set<int> dict(nums.begin(),nums.end());
		int len=0;
		for(const int &a:nums){
			if(a!=INT_MIN && dict.count(a-1)) continue;
			int right=0, i=a;
			for(; i!=INT_MAX && dict.count(i); ++i, ++right);
			len=max(len,right+(dict.count(i)?1:0));
		}
		return len;
	}
};
